import time
import tracemalloc
import math
from string_permutation import (
    permute_recursive,
    permute_iterative, 
    permute_lexicographic,
    permute_heap,
    permute_generator
)
from resource_monitor import (
    ResourceMonitor, 
    ResourceLimits, 
    safe_execute,
    format_resource_usage,
    get_safe_test_strings,
    CONSERVATIVE_LIMITS,
    MODERATE_LIMITS,
    AGGRESSIVE_LIMITS
)

class PerformanceTest:
    """性能测试类，用于验证不同排列算法的时间复杂度和空间复杂度"""
    
    def __init__(self, resource_limits: ResourceLimits = None):
        """初始化性能测试
        
        Args:
            resource_limits: 资源限制配置，默认使用适中限制
        """
        self.algorithms = {
            "递归方法": permute_recursive,
            "迭代方法": permute_iterative,
            "字典序法": permute_lexicographic,
            "Heap算法": permute_heap
        }
        
        # 生成器方法需要特殊处理
        self.generator_algorithms = {
            "生成器法": permute_generator
        }
        
        # 设置资源监控
        self.resource_monitor = ResourceMonitor(resource_limits or MODERATE_LIMITS)
        self.skipped_tests = []
        self.completed_tests = []
        
        # 算法复杂度信息
        self.complexity_info = {
            '递归方法': {
                'time': 'O(n! × n)',
                'space': 'O(n! × n) + O(n) [递归栈]',
                'description': '需要生成所有n!个排列，每个排列长度为n。递归栈深度为n。'
            },
            '迭代方法': {
                'time': 'O(n!)',
                'space': 'O(n! × n)',
                'description': '使用itertools.permutations，内部优化但仍需存储所有排列。'
            },
            '字典序法': {
                'time': 'O(n! × n)',
                'space': 'O(n! × n) + O(n)',
                'description': '原地生成下一个排列，但仍需存储所有结果。额外O(n)用于字符数组。'
            },
            'Heap算法': {
                'time': 'O(n!)',
                'space': 'O(n! × n) + O(n)',
                'description': 'Heap算法生成排列，需要O(n)递归栈空间。'
            },
            '生成器法': {
                'time': 'O(n × k)，k为已生成的排列数',
                'space': 'O(n) [仅存储当前排列]',
                'description': '使用生成器按需生成排列，空间复杂度最优。适合只需要部分排列的场景。'
            }
        }
    
    def format_time(self, seconds):
        """格式化时间显示，自动选择合适的单位"""
        if seconds >= 1:
            return f"{seconds:.3f} 秒"
        elif seconds >= 0.001:
            return f"{seconds * 1000:.3f} 毫秒"
        else:
            return f"{seconds * 1000000:.3f} 微秒"
    
    def format_memory(self, kb):
        """格式化内存显示，自动选择合适的单位"""
        if kb >= 1024:
            return f"{kb / 1024:.2f} MB"
        elif kb >= 1:
            return f"{kb:.2f} KB"
        else:
            return f"{kb * 1024:.2f} 字节"
    
    def measure_performance(self, algorithm_func, test_string, algorithm_name="未知算法"):
        """测量单个算法的性能，带资源监控"""
        
        # 检查是否应该跳过测试
        should_skip, reason = self.resource_monitor.should_skip_test(test_string, algorithm_name)
        if should_skip:
            print(f"  ⚠️  跳过测试: {reason}")
            self.skipped_tests.append({
                'algorithm': algorithm_name,
                'test_string': test_string,
                'reason': reason
            })
            return None
        
        try:
            # 使用安全执行功能
            def safe_algorithm():
                return algorithm_func(test_string)
            
            result, resource_usage = safe_execute(
                safe_algorithm, 
                limits=self.resource_monitor.limits
            )
            
            performance_data = {
                'result_count': len(result),
                'execution_time': resource_usage.execution_time,
                'peak_memory_kb': resource_usage.peak_memory_mb * 1024,
                'current_memory_kb': resource_usage.memory_mb * 1024,
                'resource_usage': resource_usage
            }
            
            self.completed_tests.append({
                'algorithm': algorithm_name,
                'test_string': test_string,
                'performance': performance_data
            })
            
            return performance_data
            
        except Exception as e:
            error_msg = f"执行失败: {str(e)}"
            print(f"  ❌ {algorithm_name}: {error_msg}")
            self.skipped_tests.append({
                'algorithm': algorithm_name,
                'test_string': test_string,
                'reason': error_msg
            })
            return None
    
    def measure_generator_performance(self, generator_func, test_string, algorithm_name="生成器算法"):
        """测量生成器算法的性能，带资源监控"""
        
        # 检查是否应该跳过测试
        should_skip, reason = self.resource_monitor.should_skip_test(test_string, algorithm_name)
        if should_skip:
            print(f"  ⚠️  跳过测试: {reason}")
            self.skipped_tests.append({
                'algorithm': algorithm_name,
                'test_string': test_string,
                'reason': reason
            })
            return None
        
        try:
            # 使用安全执行功能
            def safe_generator():
                return list(generator_func(test_string))
            
            result, resource_usage = safe_execute(
                safe_generator, 
                limits=self.resource_monitor.limits
            )
            
            performance_data = {
                'result_count': len(result),
                'execution_time': resource_usage.execution_time,
                'peak_memory_kb': resource_usage.peak_memory_mb * 1024,
                'current_memory_kb': resource_usage.memory_mb * 1024,
                'resource_usage': resource_usage
            }
            
            self.completed_tests.append({
                'algorithm': algorithm_name,
                'test_string': test_string,
                'performance': performance_data
            })
            
            return performance_data
            
        except Exception as e:
            error_msg = f"执行失败: {str(e)}"
            print(f"  ❌ {algorithm_name}: {error_msg}")
            self.skipped_tests.append({
                'algorithm': algorithm_name,
                'test_string': test_string,
                'reason': error_msg
            })
            return None
    
    def theoretical_complexity(self, n):
        """计算理论复杂度"""
        factorial_n = math.factorial(n)
        return {
            'time_complexity_factorial': factorial_n,
            'space_complexity_factorial': factorial_n
        }
    
    def run_comprehensive_test(self, test_strings=None):
        """运行综合性能测试"""
        # 如果没有指定测试字符串，使用安全的字符串列表
        if test_strings is None:
            test_strings = get_safe_test_strings(self.resource_monitor.limits.max_string_length)
        
        print("🚀 字符串排列算法综合性能测试")
        print("=" * 80)
        print(f"📊 资源限制配置:")
        print(f"   最大内存: {self.resource_monitor.limits.max_memory_mb} MB")
        print(f"   最大执行时间: {self.resource_monitor.limits.max_execution_time} 秒")
        print(f"   最大字符串长度: {self.resource_monitor.limits.max_string_length}")
        print(f"   最大阶乘值: {self.resource_monitor.limits.max_factorial:,}")
        print("=" * 80)
        
        # 重置测试记录
        self.skipped_tests = []
        self.completed_tests = []
        
        for test_string in test_strings:
            n = len(test_string)
            
            # 显示理论复杂度
            complexity = self.resource_monitor.calculate_theoretical_complexity(n)
            
            print(f"\n测试字符串: '{test_string}' (长度: {n})")
            print(f"理论时间复杂度: O(n!) = O({n}!) = {complexity['factorial']:,}")
            print(f"理论空间复杂度: O(n!) = O({n}!) = {complexity['factorial']:,}")
            
            if not complexity['is_safe']:
                print(f"⚠️  预警: 预估内存 {complexity['estimated_memory_mb']:.1f}MB, 预估时间 {complexity['estimated_time_seconds']:.3f}s")
            
            print("-" * 60)
            
            results = {}
            
            # 测试普通算法
            for algo_name, algo_func in self.algorithms.items():
                print(f"测试 {algo_name}...")
                perf_result = self.measure_performance(algo_func, test_string, algo_name)
                results[algo_name] = perf_result
                
                if perf_result is not None:
                    print(f"  结果数量: {perf_result['result_count']}")
                    print(f"  执行时间: {self.format_time(perf_result['execution_time'])}")
                    print(f"  峰值内存: {self.format_memory(perf_result['peak_memory_kb'])}")
                    print(f"  当前内存: {self.format_memory(perf_result['current_memory_kb'])}")
                    
                    # 显示资源使用警告
                    if perf_result['resource_usage'].exceeded_limits:
                        print(f"  ⚠️  资源警告: {', '.join(perf_result['resource_usage'].exceeded_limits)}")
                
                print()
            
            # 测试生成器算法
            for algo_name, generator_func in self.generator_algorithms.items():
                print(f"测试 {algo_name}...")
                perf_result = self.measure_generator_performance(generator_func, test_string, algo_name)
                results[algo_name] = perf_result
                
                if perf_result is not None:
                    print(f"  结果数量: {perf_result['result_count']}")
                    print(f"  执行时间: {self.format_time(perf_result['execution_time'])}")
                    print(f"  峰值内存: {self.format_memory(perf_result['peak_memory_kb'])}")
                    print(f"  当前内存: {self.format_memory(perf_result['current_memory_kb'])}")
                    print("  注: 生成器在实际使用中可以更节省内存")
                    
                    # 显示资源使用警告
                    if perf_result['resource_usage'].exceeded_limits:
                        print(f"  ⚠️  资源警告: {', '.join(perf_result['resource_usage'].exceeded_limits)}")
                
                print()
            
            # 性能比较
            valid_results = {k: v for k, v in results.items() if v is not None}
            if len(valid_results) > 1:
                print("性能比较:")
                
                # 找出最快的算法
                fastest_algo = min(valid_results.keys(), 
                                 key=lambda k: valid_results[k]['execution_time'])
                fastest_time = valid_results[fastest_algo]['execution_time']
                
                # 找出内存最少的算法
                lowest_memory_algo = min(valid_results.keys(), 
                                       key=lambda k: valid_results[k]['peak_memory_kb'])
                lowest_memory = valid_results[lowest_memory_algo]['peak_memory_kb']
                
                for algo_name, result in valid_results.items():
                    # 避免除零错误
                    time_ratio = result['execution_time'] / fastest_time if fastest_time > 0 else 1
                    memory_ratio = result['peak_memory_kb'] / lowest_memory if lowest_memory > 0 else 1
                    
                    print(f"  {algo_name}:")
                    print(f"    时间倍数: {time_ratio:.2f}x")
                    print(f"    内存倍数: {memory_ratio:.2f}x")
                
                print(f"\n最快算法: {fastest_algo}")
                print(f"最省内存算法: {lowest_memory_algo}")
    
    def complexity_analysis(self):
        """复杂度分析说明"""
        print("\n" + "=" * 80)
        print("算法复杂度分析")
        print("=" * 80)
        
        analysis = {
            "递归方法": {
                "时间复杂度": "O(n! × n)",
                "空间复杂度": "O(n! × n) + O(n) [递归栈]",
                "说明": "需要生成所有n!个排列，每个排列长度为n。递归栈深度为n。"
            },
            "迭代方法": {
                "时间复杂度": "O(n!)",
                "空间复杂度": "O(n! × n)",
                "说明": "使用itertools.permutations，内部优化但仍需存储所有排列。"
            },
            "字典序法": {
                "时间复杂度": "O(n! × n)",
                "空间复杂度": "O(n! × n) + O(n)",
                "说明": "原地生成下一个排列，但仍需存储所有结果。额外O(n)用于字符数组。"
            },
            "Heap算法": {
                "时间复杂度": "O(n!)",
                "空间复杂度": "O(n! × n) + O(n)",
                "说明": "Heap算法生成排列，需要O(n)递归栈空间。"
            },
            "生成器法": {
                "时间复杂度": "O(n × k)，k为已生成的排列数",
                "空间复杂度": "O(n) [仅存储当前排列]",
                "说明": "使用生成器按需生成排列，空间复杂度最优。适合只需要部分排列的场景。"
            }
        }
        
        for algo_name, info in analysis.items():
            print(f"\n{algo_name}:")
            print(f"  时间复杂度: {info['时间复杂度']}")
            print(f"  空间复杂度: {info['空间复杂度']}")
            print(f"  说明: {info['说明']}")
    
    def demonstrate_generator_advantage(self):
        """演示生成器在内存使用上的优势"""
        print("\n" + "=" * 80)
        print("生成器内存优势演示")
        print("=" * 80)
        
        test_string = "abcdef"  # 6! = 720 种排列
        print(f"测试字符串: '{test_string}' (6! = 720 种排列)")
        
        # 测试一次性生成所有排列的内存使用
        print("\n1. 一次性生成所有排列:")
        tracemalloc.start()
        all_perms = permute_iterative(test_string)
        current, peak = tracemalloc.get_traced_memory()
        tracemalloc.stop()
        print(f"   生成了 {len(all_perms)} 个排列")
        print(f"   峰值内存: {self.format_memory(peak / 1024)}")
        print(f"   当前内存: {self.format_memory(current / 1024)}")
        
        # 测试使用生成器逐个处理的内存使用
        print("\n2. 使用生成器逐个处理:")
        tracemalloc.start()
        count = 0
        for perm in permute_generator(test_string):
            count += 1
            if count == 100:  # 只处理前100个排列
                break
        current, peak = tracemalloc.get_traced_memory()
        tracemalloc.stop()
        print(f"   处理了 {count} 个排列")
        print(f"   峰值内存: {self.format_memory(peak / 1024)}")
        print(f"   当前内存: {self.format_memory(current / 1024)}")
        
        print("\n3. 实际应用场景示例:")
        print("   - 查找特定模式的排列（不需要生成所有排列）")
        print("   - 分批处理大量排列（避免内存溢出）")
        print("   - 在线算法（实时生成排列响应用户请求）")
        
        # 演示查找特定排列的场景
        print("\n4. 查找以'a'开头的前5个排列:")
        count = 0
        for perm in permute_generator(test_string):
            if perm.startswith('a'):
                print(f"   {count + 1}. {perm}")
                count += 1
                if count == 5:
                    break

    def run_performance_test(self):
        """运行完整的性能测试流程"""
        # 使用安全的测试字符串列表（根据资源限制自动确定）
        test_strings = get_safe_test_strings(self.resource_monitor.limits.max_string_length)
        
        # 运行综合测试
        self.run_comprehensive_test(test_strings)
        
        # 显示复杂度分析
        self.complexity_analysis()
        
        # 演示生成器的内存优势
        self.demonstrate_generator_advantage()
        
        # 使用建议
        print("\n" + "="*80)
        print("📋 使用建议")
        # 测试总结报告
        self.print_test_summary()
        
    def print_test_summary(self):
        """打印测试总结报告"""
        print("\n" + "="*80)
        print("📊 测试总结报告")
        print("="*80)
        
        print(f"✅ 完成测试: {len(self.completed_tests)} 个")
        print(f"⚠️  跳过测试: {len(self.skipped_tests)} 个")
        
        if self.skipped_tests:
            print("\n📋 跳过的测试:")
            for skipped in self.skipped_tests:
                print(f"   - {skipped['algorithm']} ('{skipped['test_string']}'): {skipped['reason']}")
        
        if self.completed_tests:
            print("\n🏆 性能统计:")
            
            # 按算法分组统计
            algo_stats = {}
            for test in self.completed_tests:
                algo = test['algorithm']
                if algo not in algo_stats:
                    algo_stats[algo] = {
                        'count': 0,
                        'total_time': 0.0,
                        'total_memory': 0.0,
                        'max_string_length': 0
                    }
                
                stats = algo_stats[algo]
                stats['count'] += 1
                stats['total_time'] += test['performance']['execution_time']
                stats['total_memory'] += test['performance']['peak_memory_kb']
                stats['max_string_length'] = max(stats['max_string_length'], len(test['test_string']))
            
            for algo, stats in algo_stats.items():
                avg_time = stats['total_time'] / stats['count']
                avg_memory = stats['total_memory'] / stats['count']
                print(f"   {algo}: {stats['count']} 次测试, 平均时间 {self.format_time(avg_time)}, 平均内存 {self.format_memory(avg_memory)}, 最大长度 {stats['max_string_length']}")
        
        print("\n📋 使用建议")
        print("="*80)
        print("1. 🔹 小规模数据(n ≤ 8): 任何算法都可以")
        print("2. 🔸 中等规模数据(8 < n ≤ 10): 推荐使用迭代方法或Heap算法")
        print("3. 🔶 大规模数据(n > 10): 考虑是否真的需要生成所有排列")
        print("4. 💾 内存敏感场景: 使用生成器模式，逐个生成排列")
        print("5. 📚 字典序要求: 使用字典序法")
        print("6. 🎓 教学目的: 递归方法最直观易懂")
        print("7. 🔍 查找特定排列: 使用生成器法，可以提前终止")
        print("8. ⚡ 高性能要求: 使用迭代方法(itertools.permutations)")
        
        print(f"\n🔧 当前资源限制:")
        print(f"   - 最大内存: {self.resource_monitor.limits.max_memory_mb} MB")
        print(f"   - 最大执行时间: {self.resource_monitor.limits.max_execution_time} 秒") 
        print(f"   - 最大字符串长度: {self.resource_monitor.limits.max_string_length}")
        print(f"   - 最大阶乘值: {self.resource_monitor.limits.max_factorial:,}")


def main():
    """主测试函数"""
    import sys
    
    # 根据命令行参数选择资源限制级别
    if len(sys.argv) > 1:
        limit_type = sys.argv[1].lower()
        if limit_type == "conservative":
            limits = CONSERVATIVE_LIMITS
            print("🔒 使用保守资源限制")
        elif limit_type == "aggressive":
            limits = AGGRESSIVE_LIMITS
            print("⚡ 使用激进资源限制")
        else:
            limits = MODERATE_LIMITS
            print("⚖️  使用适中资源限制")
    else:
        limits = MODERATE_LIMITS
        print("⚖️  使用适中资源限制 (默认)")
    
    # 创建性能测试实例
    perf_test = PerformanceTest(limits)
    
    # 运行完整的性能测试
    perf_test.run_performance_test()


if __name__ == "__main__":
    main()
